public void reversePrintList(ListNode head) {
	
	if (head == null) return;
	if (head != null) {
		reversePrintList(head.next);
		System.out.print(head.val + " ");
	}
}

public void reversePrintList(ListNode head) {
	
	Stack<ListNode> stack = new Stack<>();
	ListNode cur = head;
	
	while (cur != null) {
		stack.push(cur);
		cur = cur.next;
	}
	while (!stack.isEmpty()){
		ListNode top = stack.pop();
		System.out.print(top.vale + " ");
	}
}

public boolean isValid(String s) {
	
	Stack<Character> stack = new Stack<>();
	
	// 遍历所有括号
	for(int i = 0; i < s.length(); i++) {
		
		char ch = s.charAt(i);
		
		// 如果是左括号，则直接入栈
		if (ch == '(' || ch == '{' || ch == '[') {
			stack.push(ch);
		} else {
			// 如果是右括号
			// 先判断栈中是否有左括号
			if (stack.isEmpty()) return false;
			char top = stack.peek();
			if ((top == '(' && ch == ')') || (top == '{' && ch == '}') || (top == '[' && ch == ']') {
				stack.pop();
			} else {
				// 无法匹配，返回false
				return false;
			}
		}
	}
	if (!stack.isEmpty()) {
		return false;
	}
}


// 中缀表达式转变为后缀表达式：
// 1. 从左到右，按照先乘除，后加减的顺序，对表达式加括号
// 2. 将对应括号中的算术符号提出括号外
// 3. 将括号全部删除~~~

// 后缀表达式做计算使用：
// 定义一个变量 i 遍历整个表达式
// 遇到数字，就将数字放入栈中，如果遇到符号，则将栈顶两个元素弹出，第一个弹出的元素做为右操作数，第二个弹出的元素作为左操作数
// 将计算完毕后的结果再放入栈中~~


public int evalRPN(String[] tokens) {
	
	Stack<Integer> stack = new Stack<>();
	for(String s : tokens) {
		if (!isOperation(s)) {
			// 如果是数字的话，将数字压栈
			stack.push(Integer.parseInt(s));
		} else {
			// 如果是算数符号，则将两个栈顶元素弹出，第一个弹出的元素做为右操作数，第二个弹出的元素作为左操作数
			int num2 = stack.pop();
			int num1 = stack.pop();
			switch(s) {
				case "+" :
				stack.push(num1 + num2);
				break;
				
				case "-" :
				stack.push(num1 - num2);
				break;
				
				case "*" :
				stack.push(num1 * num2);
				break;
			
				case "/":
				stack.push(num1 / num2);
				break;
			}
		}
	}
	return stack.pop();
}

private boolean isOperation(String s){
	if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
		return true;
	}
	return false;
}



public boolean IsPopOrder (int[] pushA, int[] popA) {
	
	// 边界条件
	if (pushA.length != popA.length) {
		return false;
	}
	
	if (pushA.length == 0) {
            return true;
    }
		
	Stack<Integer> stack = new Stack<>();
	// 遍历 popA 的下标
	int j = 0;
	
	for (int i = 0 ; i < pushA.length; i++) {
		stack.push(pushA[i]);
		
		while (!stack.isEmpty() && j < popA.length && stack.peek() == popA[j]) {
			stack.pop();
			j++;
		}
	}
	
	if (stack.isEmpty()){
		return true;
	}
	return false;
}

class minStack{
	
	private Stack<Integer> stack;
	private Stack<Integer> minStack;
	
	public minStack(){
		stack = new Stack<>();
		minStack = new Stack<>();
	}
	
	public void push(int val) {
		stack.push(val);
		if (minStack.isEmpty()) {
			minStack.push(val);
		} else {
			if (val <= minStack.peek()) {
				minStack.push(val);
			}
		}
	}
	
	public int pop(){
		int ret = stack.pop();
		if (ret == minStack.peek()){
			minStack.pop();
		}
		return ret;
	}
	
	public int top() {
		if (stack.isEmpty()) {
			return -1;
		}
		return stack.peek();
	}
	
	public int getMin() {
		if (minStack.isEmpty()){
			return -1;
		}
		return minStack.peek();
	}
	
}